1 bit and 2 bit characters [Greedy]

Time: O(N); Space: O(1); easy

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

Input: bits = [1, 0, 0]

Output: True

Explanation:

  • The only way to decode it is two-bit character and one-bit character.

  • So the last character is one-bit character.

Example 2:

Input: bits = [1, 1, 1, 0]

Output: False

Explanation:

  • The only way to decode it is two-bit character and two-bit character.

  • So the last character is NOT one-bit character.

Note:

  • 1 <= len(bits) <= 1000.

  • bits[i] is always 0 or 1.

Hints:

  1. Keep track of where the next character starts. At the end, you want to know if you started on the last bit.

[1]:

class Solution1(object):
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        parity = 0
        for i in reversed(range(len(bits)-1)):
            if bits[i] == 0:
                break
            parity ^= bits[i]
        return parity == 0

[2]:

s = Solution1()
bits = [1, 0, 0]
assert s.isOneBitCharacter(bits) == True
bits = [1, 1, 1, 0]
assert s.isOneBitCharacter(bits) == False